/**
 * Created with IntelliJ IDEA.
 * Description :
 * User: $ {USER}
 * Date: $ {YEAR}-$ {MONTH}一$ { DAY}
 * Time: ${ TIME}
 */

/**
 * 题目：翻转二叉树
 * 思路：1. 先把二叉树的头结点的left值和right值交换，头结点弄完之后，就递归左子树和右子树。遇到叶子结点就返回
 *      2. 与上面一种情况刚好相反，先递归到叶子结点的上一级开始交换叶子结点，再交换本级根结点的left值和right值
 */
public class Test {
    // 这个相对于官方题解易于理解
    // public TreeNode invertTree(TreeNode root) {
    //     if (root == null) {
    //         return root;
    //     }
    //     // 当结点两侧值都为null时，就可以不用交换
    //     // 当结点两侧的值相同时，(本级)翻转的结果不变，但后级的值不确定，因此只能为null时使用
    //     if (root.left == null && root.right == null) {
    //         return root;
    //     }
    //     // 先翻转根结点
    //     TreeNode tmp = root.left;
    //     root.left = root.right;
    //     root.right = tmp;
    //     // 翻转左子树
    //     invertTree(root.left);
    //     // 翻转右子树
    //     invertTree(root.right);
    //     return root;
    // }


    // 官方题解的方式
    public TreeNode invertTree(TreeNode root) {
        if (root == null) {
            return root;
        }
        // 叶子结点直接返回即可
        if (root.left == null && root.right == null) {
            return root;
        }
        // 翻转左子树的结果
        TreeNode leftTree = invertTree(root.left);
        // 翻转右子树的结果
        TreeNode rightTree = invertTree(root.right);
        // 开始交换本级根的左子树和右子树
        root.left = rightTree;
        root.right = leftTree;
        return root;
    }
}


class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode() {
    }

    TreeNode(int val) {
        this.val = val;
    }

    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}
